
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1447. -- Moving the Hay -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1447: Moving the Hay</h2><span class=green>Time Limit: </span>5 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>52&nbsp;&nbsp;<span class=green>Solved: </span>21<br>[<a href='submitpage.php?id=1447'>Submit</a>][<a href='problemstatus.php?id=1447'>Status</a>][<a href='bbs.php?id=1447'>Discuss</a>]</center><h2>Description</h2><div class=content>

After he partitioned his farm into R (1 <= R <= 200) rows and C (1
<= C <= 200) squares conveniently labeled 1,1 through R,C, Farmer
John spent days cutting the hay and stacking a huge amount of it
in square 1,1. He then undertook the task of mapping out the N (1
<= N <= 80,000) haypaths through the farm so that he could deduce
the maximum rate he could move hay from square 1,1 to square R,C.

Each haypath uniquely connects the middle of two rectilinearly
adjacent partitioned squares and has some capacity limit L_i (1 <=
L_i <= 20,000,000) that is the maximum amount of hay that can be
transported in either direction across the haypath.  He's just
positive that he can move hay at a reasonable rate to the other
side of the farm but he doesn't know what the fastest rate is. Help
him learn it.
</div><h2>Input</h2><div class=content>* Line 1: Three separated integers: R, C, and N
* Lines 2..N+1: Line i+1 describes path i with five space-separated
        integers: r1, c1, r2, c2, and L_i which denote a haypath
        connecting (r1,c1) to (r2,c2) with capacity L_i.

</div><h2>Output</h2><div class=content>
* Line 1: One number, on a line by itself, the maximum amount of
        material which can be transported from (1,1) to (R,C)
        simultaneously.
</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata><br />
3 3 8<br />
1 1 1 2 5<br />
1 1 2 1 3<br />
1 2 2 2 5<br />
2 1 2 2 2<br />
2 2 2 3 1<br />
2 2 3 2 6<br />
2 3 3 3 4<br />
3 2 3 3 7<br />
<br />
INPUT DETAILS:<br />
<br />
The grid is as follows:<br />
*--5--* . . *<br />
|     |     <br />
3     5     :<br />
|     |    <br />
*--2--*--1--*<br />
      |     |<br />
:     6     4<br />
      |     |<br />
* . . *--7--*<br />
    <br />
<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>7<br />
<br />
</span></div><h2>HINT</h2>
			<div class=content><p><br />
Consider the two edges coming out of (2,2), at most 6+1=7 units of hay can<br />
be transported. This is indeed feasible.<br />
</p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search='></a></p></div><center>[<a href='submitpage.php?id=1447'>Submit</a>][<a href='problemstatus.php?id=1447'>Status</a>][<a href='bbs.php?id=1447'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
